package com.lik.javadeep.basic.sort;

public class MergeSortRepeat {
    public static void main(String[] args) {
        int[] ints = {9, 3, 5, 2, 9, 6, 18};
        divideAndSort(ints, 0, ints.length);

        for (int i : ints) {
            System.out.println(i);
        }

    }


    private static void divideAndSort(int[] arrays, int lo, int high) {
        // 只有一个元素，不必再分
        if (high - lo < 2) {
            return;
        }

        int middle = (lo + high) >> 1;

        // 左、右子数组
        int[] left = new int[middle - lo];
        int[] right = new int[high - middle];


        for (int k = 0; k < left.length; k++) {
            left[k] = arrays[k];
        }
        for (int k = middle - lo, i = 0; i < right.length; k++) {
            right[i] = arrays[k];
            i++;
        }


        divideAndSort(left, lo, middle);
        divideAndSort(right, middle, high);
        merge(left, right, arrays);
    }

    private static void merge(int[] left, int[] right, int[] temp) {
        int l = 0, r = 0, t = 0;
        while (l < left.length && r < right.length) {
            if (left[l] > right[r]) {
                temp[t++] = right[r++];
            } else {
                temp[t++] = left[l++];
            }
        }

        while (r < right.length) {
            temp[t++] = right[r++];
        }

        while (l < left.length) {
            temp[t++] = left[l++];
        }
    }
}
